package com.jonlandrum.collections.BinarySearchTree;

import org.junit.Test;

import java.util.NoSuchElementException;

import static org.junit.Assert.*;

public class LinkedBinarySearchTreeTest {
    @Test
    public void testEmptyConstructor() {
        LinkedBinarySearchTree tree = new LinkedBinarySearchTree<>();
        assertEquals(null, tree.getRoot());
    }

    @Test
    public void testNodeConstructor() {
        LinkedBinarySearchTree tree = new LinkedBinarySearchTree<>(new LinkedBinarySearchNode<>("root"));
        assertEquals("root", tree.getRoot().toString());
    }

    @Test
    public void testGetRoot_RootIsNull() {
        LinkedBinarySearchTree testGetRoot = new LinkedBinarySearchTree<>();
        assertEquals(null, testGetRoot.getRoot());
    }

    @Test
    public void testGetRoot_RootIsNotNull() {
        LinkedBinarySearchTree testGetRoot = new LinkedBinarySearchTree<>(new LinkedBinarySearchNode<>("test"));
        assertEquals("test", testGetRoot.getRoot().toString());
    }

    @Test
    public void testSetRootToNull() {
        LinkedBinarySearchTree testSetRoot = new LinkedBinarySearchTree<>(new LinkedBinarySearchNode<>("test"));
        assertEquals("test", testSetRoot.getRoot().toString());
        testSetRoot.setRoot();
        assertEquals(null, testSetRoot.getRoot());
    }

    @Test
    public void testSetRootToNode() {
        LinkedBinarySearchTree<String> testSetRoot = new LinkedBinarySearchTree<>();
        assertEquals(null, testSetRoot.getRoot());
        testSetRoot.setRoot(new LinkedBinarySearchNode<>("test"));
        assertEquals("test", testSetRoot.getRoot().toString());
    }

    @Test
    public void testHasRoot() {
        LinkedBinarySearchTree<String> testHasRoot = new LinkedBinarySearchTree<>();
        assertFalse(testHasRoot.hasRoot());
        testHasRoot.setRoot(new LinkedBinarySearchNode<>("root"));
        assertTrue(testHasRoot.hasRoot());
    }

    @Test
    public void testInsertIntoEmptyTree() {
        LinkedBinarySearchTree<String> testInsert = new LinkedBinarySearchTree<>();
        assertFalse(testInsert.hasRoot());
        testInsert.insert("1");
        assertTrue(testInsert.hasRoot());
    }

    @Test
    public void testInsertIntoNonEmptyTree_InsertionPointGreaterThanElement() {
        LinkedBinarySearchTree<String> testInsert = new LinkedBinarySearchTree<>();
        testInsert.insert("10");
        assertTrue(testInsert.hasRoot());
        testInsert.insert(new LinkedBinarySearchNode<>("1"));
        assertTrue(testInsert.getRoot().getLeft().toString().equals("1"));
    }

    @Test
    public void testInsertIntoNonEmptyTree_InsertionPointLessThanElement() {
        LinkedBinarySearchTree<String> testInsert = new LinkedBinarySearchTree<>();
        testInsert.insert("1");
        assertTrue(testInsert.hasRoot());
        testInsert.insert(new LinkedBinarySearchNode<>("10"));
        assertTrue(testInsert.getRoot().getRight().toString().equals("10"));
    }

    @Test(expected = NoSuchElementException.class)
    public void testDeleteFromEmptyTree() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.delete(1);
    }

    @Test
    public void testDeleteFromNonEmptyTree_NoSuccessor_TargetIsLeftLeaf() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(10);
        testDelete.insert(1);
        assertTrue(testDelete.getRoot().hasLeft());
        testDelete.delete(1);
        assertFalse(testDelete.getRoot().hasLeft());
    }

    @Test
    public void testDeleteFromNonEmptyTree_NoSuccessor_TargetIsRightLeaf() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(10);
        testDelete.insert(100);
        assertTrue(testDelete.getRoot().hasRight());
        testDelete.delete(100);
        assertFalse(testDelete.getRoot().hasRight());
    }

    @Test
    public void testDeleteFromNonEmptyTree_NoSuccessor_TargetIsRoot() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>(new LinkedBinarySearchNode<>(10));
        assertTrue(testDelete.hasRoot());
        testDelete.delete(10);
        assertFalse(testDelete.hasRoot());
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsLeftChild_SuccessorHasLeftChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(100);
        testDelete.insert(10);
        testDelete.insert(1);
        assertTrue(testDelete.getRoot().hasLeft());
        testDelete.delete(100);
        assertTrue(testDelete.getRoot().toString().equals("10"));
        assertTrue(testDelete.getRoot().hasLeft());
        assertTrue(testDelete.getRoot().getLeft().toString().equals("1"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsLeftChild_SuccessorHasRightChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(10);
        testDelete.insert(80);
        testDelete.insert(70);
        testDelete.insert(75);
        assertTrue(testDelete.getRoot().toString().equals("10"));
        testDelete.delete(10);
        assertTrue(testDelete.getRoot().toString().equals("70"));
        assertTrue(testDelete.getRoot().getRight().hasLeft());
        assertTrue(testDelete.getRoot().getRight().getLeft().toString().equals("75"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsLeftChild_SuccessorHasNoChildren() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(10);
        testDelete.insert(1);
        assertTrue(testDelete.getRoot().toString().equals("10"));
        assertTrue(testDelete.getRoot().hasLeft());
        assertTrue(testDelete.getRoot().getLeft().toString().equals("1"));
        testDelete.delete(10);
        assertTrue(testDelete.getRoot().toString().equals("1"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsRightChild_SuccessorHasLeftChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(100);
        testDelete.insert(10);
        testDelete.insert(20);
        testDelete.insert(15);
        assertTrue(testDelete.getRoot().toString().equals("100"));
        testDelete.delete(100);
        assertTrue(testDelete.getRoot().toString().equals("20"));
        assertTrue(testDelete.getRoot().getLeft().hasRight());
        assertTrue(testDelete.getRoot().getLeft().getRight().toString().equals("15"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsRightChild_SuccessorHasRightChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(1);
        testDelete.insert(10);
        testDelete.insert(100);
        assertTrue(testDelete.getRoot().toString().equals("1"));
        testDelete.delete(1);
        assertTrue(testDelete.getRoot().toString().equals("10"));
        assertTrue(testDelete.getRoot().hasRight());
        assertTrue(testDelete.getRoot().getRight().toString().equals("100"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_SuccessorIsRightChild_SuccessorHasNoChildren() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(1);
        testDelete.insert(10);
        assertTrue(testDelete.getRoot().toString().equals("1"));
        assertTrue(testDelete.getRoot().hasRight());
        assertTrue(testDelete.getRoot().getRight().toString().equals("10"));
        testDelete.delete(1);
        assertTrue(testDelete.getRoot().toString().equals("10"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_TargetHasLeftChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(100);
        testDelete.insert(10);
        testDelete.insert(1);
        testDelete.delete(10);
        assertTrue(testDelete.getRoot().toString().equals("100"));
        assertTrue(testDelete.getRoot().getLeft().toString().equals("1"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_TargetHasRightChild() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(1);
        testDelete.insert(10);
        testDelete.insert(100);
        testDelete.delete(10);
        assertTrue(testDelete.getRoot().toString().equals("1"));
        assertTrue(testDelete.getRoot().getRight().toString().equals("100"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_TargetHasParent() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(1);
        testDelete.insert(10);
        testDelete.insert(100);
        assertTrue(testDelete.getRoot().getRight().getParent().toString().equals("1"));
        assertTrue(testDelete.getRoot().getRight().toString().equals("10"));
        testDelete.delete(10);
        assertTrue(testDelete.getRoot().getRight().getParent().toString().equals("1"));
        assertTrue(testDelete.getRoot().getRight().toString().equals("100"));
    }

    @Test
    public void testDeleteFromNonEmptyTree_TargetIsRoot() {
        LinkedBinarySearchTree<Integer> testDelete = new LinkedBinarySearchTree<>();
        testDelete.insert(1);
        testDelete.insert(10);
        assertTrue(testDelete.getRoot().getRight().getParent().toString().equals("1"));
        assertTrue(testDelete.getRoot().getRight().toString().equals("10"));
        testDelete.delete(1);
        assertTrue(testDelete.getRoot().toString().equals("10"));
    }

    @Test(expected = NoSuchElementException.class)
    public void testSearchEmptyTree() {
        LinkedBinarySearchTree<Integer> testSearch = new LinkedBinarySearchTree<>();
        testSearch.search(1);
    }

    @Test(expected = NoSuchElementException.class)
    public void testSearchNonEmptyTree_NonExistingElement() {
        LinkedBinarySearchTree<Integer> testSearch = new LinkedBinarySearchTree<>();
        testSearch.insert(1);
        testSearch.search(10);
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsRoot() {
        LinkedBinarySearchTree<Integer> testSearch = new LinkedBinarySearchTree<>();
        testSearch.insert(1);
        assertTrue(testSearch.search(1).toString().equals("1"));
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsInternalNode() {
        LinkedBinarySearchTree<Integer> testSearch = new LinkedBinarySearchTree<>();
        testSearch.insert(10);
        testSearch.insert(1);
        testSearch.insert(100);
        testSearch.insert(5);
        testSearch.insert(50);
        testSearch.insert(0);
        testSearch.insert(200);
        assertTrue(testSearch.search(1).toString().equals("1"));
    }

    @Test
    public void testSearchNonEmptyTree_ExistingElement_TargetIsLeaf() {
        LinkedBinarySearchTree<Integer> testSearch = new LinkedBinarySearchTree<>();
        testSearch.insert(10);
        testSearch.insert(1);
        testSearch.insert(100);
        testSearch.insert(5);
        testSearch.insert(50);
        testSearch.insert(0);
        testSearch.insert(200);
        assertTrue(testSearch.search(200).toString().equals("200"));
    }
}